package interview8;

/**
 * @author Jack
 * @date 2019-11-05-11:09
 */
public class Solution {

    public Node getNextNodeByInOrder(Node node) {
        if (node == null) {
            return null;
        }
        Node temp = null;
        if (node.rightChild != null) {
            temp = node.rightChild;
            while (temp.leftChild != null) {
                temp = temp.leftChild;
            }
        } else if (node.father != null && node == node.father.leftChild) {
            temp = node.father;
        } else if (node.father != null && node == node.father.rightChild) {
            boolean isLastNode = true;
            temp = node.father;
            while (temp.father != null) {
                temp = temp.father;
                if (temp.father != null && temp == temp.father.leftChild) {
                    temp = temp.father;
                    isLastNode = false;
                    break;
                }
            }
            if (isLastNode) {
                temp = null;
            }
        }
        return temp;
    }

}

class Node {
    String value;
    Node leftChild;
    Node rightChild;
    Node father;

    public Node(String value) {
        super();
        this.value = value;
    }


}